While the priority queue approach we just set up is the most efficient, it's valuable to first understand a more direct implementation. This method uses an adjacency matrix to represent the graph $G = (V, E)$ and simple arrays to track state, providing a clear baseline for appreciating more advanced data structures.

  • Graph Representation: An adjacency matrix $M$ is a $V \times V$ grid where $M[i][j]$ stores the weight $w(i, j)$. Non-existent edges are represented by infinity.
  • State Tracking: Uses two arrays: a boolean `in_mst` array to mark vertices already in the MST, and a `key` array where `key[i]` stores the minimum edge weight connecting vertex $i$ to the MST.
  • The critical performance bottleneck comes from selecting the next vertex. In each step, we must perform a linear scan through the `key` array to find the unvisited vertex with the minimum key value.
  • This nested loop structure—an outer loop running $V$ times and an inner loop scanning $V$ vertices—leads to its $O(V^2)$ time complexity.
Python: Prim's with Matrix and Array
1import sys
2
3def prims_matrix(graph_matrix):
4    V = len(graph_matrix)
5    parent = [None] * V  # Stores the constructed MST
6    key = [sys.maxsize] * V   # Key values used to pick minimum weight edge
7    in_mst = [False] * V  # To represent set of vertices included in MST
8
9    key[0] = 0      # Start with the first vertex
10    parent[0] = -1  # First node is always the root of MST
11
12    for _ in range(V):
13        # 1. Find the unvisited vertex with the minimum key value
14        min_key = sys.maxsize
15        min_index = -1
16        for v in range(V): # This is the O(V) linear scan
17            if not in_mst[v] and key[v] < min_key:
18                min_key = key[v]
19                min_index = v
20        
21        # 2. Add the picked vertex to the MST Set
22        u = min_index
23        in_mst[u] = True
24
25        # 3. Update key values of adjacent vertices
26        for v in range(V):
27            if graph_matrix[u][v] > 0 and not in_mst[v] and graph_matrix[u][v] < key[v]:
28                key[v] = graph_matrix[u][v]
29                parent[v] = u
30    return parent
31
32# Using Shared_Graph (A=0, B=1, C=2, D=3, E=4, F=5)
33# 0 indicates no direct edge for simplicity
34graph = [[0, 4, 3, 0, 0, 0], [4, 0, 1, 5, 0, 0], [3, 1, 0, 2, 6, 0],
35         [0, 5, 2, 0, 8, 7], [0, 0, 6, 8, 0, 9], [0, 0, 0, 7, 9, 0]]
36
37mst = prims_matrix(graph)
38print("MST (Parent Array):", mst)